package 二叉树高频题目_上_不含树型dp;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class Code07_PreorderInorderBuildBinaryTree {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length != inorder.length){
            return null;
        }
        int l1 = 0;
        int r1 = preorder.length-1;
        int l2 = 0;
        int r2 = inorder.length-1;
        // 空间换时间，使用map结构，存储中序遍历的数组，
        // 这样就可以快速，从先序遍历的头结点中找到对应节点的下标。
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return fun(preorder, l1, r1, inorder, l2, r2, map);
    }

    public TreeNode fun(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map){
        if(l1 > r1){
            return null;
        }
        TreeNode head = new TreeNode(pre[l1]);
        if(l1 == r1){
            return head;
        }
        // 根据先序遍历的头结点来看中序遍历的来区分左右子树的节点的位置
        int k = map.get(pre[l1]);
        // pre : l1(........)[.......r1]
        // in  : (l2......)k[........r2]
        // (...)是左树对应，[...]是右树的对应，进行递归遍历
        head.left = fun(pre, l1+1, l1+k-l2, in, l2, k-1, map);
        head.right = fun(pre, l1+k-l2+1, r1, in, k+1, r2, map);
        return head;
    }
}
